package com.atguigu.srb.base.algorithm;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName ff
 * @Describe
 * @Author Wangchengshan
 * @Date 2023/5/30 16:00
 * @Version 1.0
 **/
public class ff {
    public static void main(String[] args) {
        int nums[]={1,-1,-2,4,-7,3};
        System.out.println(maxResult(nums,2));

    }
    public static int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        Deque<Integer> deque = new LinkedList<>();
        deque.offerLast(0);
        for (int i = 1; i < n; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }
            dp[i] = dp[deque.peekFirst()] + nums[i];
            while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        return dp[n - 1];
    }
}
